package problems.contest;

import java.util.*;

/**
 * @author habitplus
 * @since 2022/7/31 10:29
 */
public class WCT304 {
    /**
     * T1
     */
    public int minimumOperations(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int n = nums.length;
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int ans = 0;
        while (maxNum != 0) {
            // 找最小的数
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num > 0) min = Math.min(min, num);
            }

            if (min == Integer.MAX_VALUE) break;

            for (int i = 0; i < n; i++) {
                if (nums[i] > 0)
                    nums[i] -= min;
            }
            maxNum -= min;
            ans++;
        }

        return ans;
    }


    /**
     * T2
     */
    public int maximumGroups(int[] grades) {
        int n = grades.length;

        int g = 0;
        // 1 + 2 + 3 + ... + g <= 2 * len
        while ((g + 1) * g < 2 * n) {
            g++;
        }


        if ((g + 1) * g == 2 * n) return g;
        else return g - 1;
    }


    /**
     * T3
     */
    Map<Integer, Integer> dis = new HashMap<>();
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        // 找出 从 node1 到各个可达点的最小距离
        if (node1 == node2) return -1;
        Map<Integer, Integer> map1 = bfs(edges, node1);
        Map<Integer, Integer> map2 = bfs(edges, node2);

        int dis = Integer.MAX_VALUE;
        int ans = -1;
        for (Map.Entry<Integer, Integer> e : map1.entrySet()) {
            int key = e.getKey();
            if (map2.containsKey(key)) {
                if (Math.max(e.getValue(), map2.get(key)) < dis) {
                    dis = Math.max(e.getValue(), map2.get(key));
                    ans = key;
                }
            }
        }
        return ans;
    }

    private Map<Integer, Integer> bfs(int[] edges, int node) {
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();
        int steps = 0;
        que.offer(node);
        set.add(node);
        while (!que.isEmpty()) {

            for (int i = que.size(); i > 0; i--) {
                int j = que.poll();
                int nxt = edges[j];
                map.put(j, steps);
                if (nxt > -1 && !set.contains(nxt)) {
                    que.offer(nxt);
                    set.add(nxt);
                }
            }
            steps++;
        }
        return map;
    }
}
